#ifndef _AVRSTDC_SLIST_H_
#define _AVRSTDC_SLIST_H_

//NOTE: assert() can be disabled at compile-time defining -DNDEBUG during compilation
#include <assert.h>

template <class T> class SList;
template <class T> class SListIterator;
template <class T> class SListManipulator;

template<class T>
class SListNode
{
private:
	T	contents;
	SListNode<T> * next;

	SListNode(const T& Contents, SListNode * Next)
	: contents(Contents), next(Next) { }

	friend class SList<T>;
	friend class SListIterator<T>;
	friend class SListManipulator<T>;
};

template<class T>
class SList
{
public:
	SList();
	SList(const T&);
	SList(const SList &);
	SList<T> & operator = (const SList &);
	virtual ~SList();

	virtual void Insert(const SList<T> &);
	virtual void Insert(const T&);
	virtual T 	 ExtractHead();
	virtual bool Empty() const;
	virtual T *	 Head() const;
	virtual T *	 Extract(const T&);
	virtual uint16 Size() const { return size; }

	friend class SListIterator<T>;
	virtual SListIterator<T> Iterator() const;

	friend class SListManipulator<T>;
	virtual SListManipulator<T> Manipulator();

protected:
	uint16		size;
	uint8		numIterators;
	uint8		numManipulators;
	SListNode<T> * head;
};

template<class T>
class SListIterator
{
public:
	SListIterator(const SListIterator<T> &);
	SListIterator<T> & operator = (const SListIterator<T> &);
	virtual ~SListIterator();

	virtual void	Reset();
	virtual void	Detach();
	virtual T&		operator*();
	virtual const T& operator*() const;
	virtual operator bool() const;
	virtual void	operator++(int);

protected:
	SList<T> *	list;
	SListNode<T> * ptr;

private:
	SListIterator(SList<T> *);

	friend class SList<T>;
	friend class SListManipulator<T>;
};

template<class T>
class SListManipulator
{
public:
	SListManipulator(const SListManipulator<T> &);
	SListManipulator<T> & operator = (const SListManipulator<T> &);
	virtual ~SListManipulator();

	virtual void	Reset();
	virtual void	Detach();
	virtual void	operator++(int);
	virtual void	Insert(const T&);
	virtual void	Delete();

protected:
	SList<T> *		list;
	SListNode<T> *	ptr;
	SListNode<T> * 	prev;
		
private:
	SListManipulator(SList<T> *);

	friend class SList<T>;
};

///////////////////////////////////[class Definitions 
template<class T>
SList<T>::SList()
{
	head = 0;
	size = 0;
	numIterators = numManipulators = 0;
}

template<class T>
SList<T>::SList(const T& contents)
{
	head = new SListNode<T>(contents,0);
	size = 1;
}

template<class T>
SList<T>::SList(const SList<T> & list)
{
	head = 0;
	size = 0;
	numIterators = numManipulators = 0;

	for( SListNode<T> * sn = list.head; sn; sn = sn->next)
		Insert(sn->contents);
}

template<class T>
SList<T> &
SList<T>::operator = (const SList<T> & list)
{
	SListNode<T> *	sn;
	for (sn = head; sn; )
	{
		SListNode<T> * temp = sn->next;
		delete sn;
		sn = temp;
	}
	head = 0; size = 0;
	numIterators = numManipulators = 0;
	for (sn = list.head; sn; sn = sn->next)
		Insert(sn->contents);

	return *this;
}

template<class T>
SList<T>::~SList()
{
	assert(numIterators == 0);
	assert(numManipulators == 0);

	SListNode<T> * sc = head;
	while(sc)
	{
		SListNode<T> * temp = sc->next;
		delete sc;
		sc = temp;
	}
}

template<class T>
void
SList<T>::Insert(const SList<T> & list)
{
	assert(numIterators == 0);
	assert(numManipulators == 0);

	for( SListNode<T> * sln = list.head; sln; sln = sln->next)
		Insert(sln->contents);
}

template<class T>
void
SList<T>::Insert(const T& contents)
{
	assert(numIterators == 0);
	assert(numManipulators == 0);

	head = new SListNode<T>(contents,head);
	++size;
}

template<class T>
T
SList<T>::ExtractHead()
{
	assert(numIterators == 0);
	assert(numManipulators == 0);
	assert(size);

	if (head)
	{
		T	ret;
		SListNode<T> * temp = head->next;
		ret = head->contents;
		delete head;
		head = temp;
		--size;
		return ret;
	}
}

template<class T>
bool
SList<T>::Empty() const
{
	return (size == 0);
}

template<class T>
T *
SList<T>::Head() const
{
	assert(size);
	return &head->contents;
}

template<class T>
T *
SList<T>::Extract(const T& contents)
{
	SListNode<T> * sln;
	for (sln = head; sln; sln = sln->next)
	{
		if (sln->contents == contents)
			return &sln->contents;
	}
	return 0;
}

template<class T>
SListIterator<T>
SList<T>::Iterator() const
{
	assert(numManipulators == 0);

	((SList<T>*)this)->numIterators += 1;

	return SListIterator<T>((SList<T>*)this);
}

template<class T>
SListManipulator<T>
SList<T>::Manipulator()
{
	assert(numIterators == 0);
	assert(numManipulators == 0);

	((SList<T>*)this)->numManipulators += 1;

	return SListManipulator<T>((SList<T>*)this);
}

//------------------[class SListIterator
template<class T>
SListIterator<T>::SListIterator(SList<T> * List)
{
	list = List;
	ptr  = List->head;
}

template<class T>
SListIterator<T>::SListIterator(const SListIterator<T> & iter)
{
	list = iter.list;
	ptr = iter.ptr;
	if (list)
		++(list->numIterators);
}

template<class T>
SListIterator<T> &
SListIterator<T>::operator = (const SListIterator<T> & iter)
{
	--(list->numIterators);
	list = iter.list;
	ptr = iter.ptr;
	++(list->numIterators);
	return *this;
}

template<class T>
SListIterator<T>::~SListIterator()
{
	if (list)
	--(list->numIterators);
}

template<class T>
void
SListIterator<T>::Detach()
{
	assert(list);

	ptr = 0;
	--(list->numIterators);
	list = 0;
}

template<class T>
void
SListIterator<T>::Reset()
{
	assert(list);

	ptr = list->head;
}

template<class T>

SListIterator<T>::operator bool() const
{
	return (ptr != 0);
}

template<class T>
T &
SListIterator<T>::operator * ()
{
	assert(ptr);

	return ptr->contents;
}

template<class T>
const T&
SListIterator<T>::operator * () const
{
	assert(ptr);

	return ptr->contents;
}

template<class T>
void
SListIterator<T>::operator ++ (int)
{
	assert(ptr);

	ptr = ptr->next;
}

//------------------[class SListManipulator]
template<class T>
SListManipulator<T>::SListManipulator(SList<T> * List)
{
	list = List;
	ptr = prev = 0;
}

template<class T>
SListManipulator<T>::~SListManipulator()
{
	if (list)
		--(list->numManipulators);
	list = 0;
}

template<class T>
void
SListManipulator<T>::Detach()
{
	ptr = prev = 0;
	--(list->numManipulators);
	list = 0;
}

template<class T>
void
SListManipulator<T>::Reset()
{
	//TODO SListIterator<T>::Reset();
	prev = 0;
}

template<class T>
void
SListManipulator<T>::operator ++ (int)
{
	assert(ptr);
	prev = ptr;
	ptr = ptr->next;
}

template<class T>
void
SListManipulator<T>::Insert(const T& contents)
{
	if (list->Empty())
		list->Insert(contents);
	else
	{
		SListNode<T> * node = new SListNode<T>(contents,ptr);
		prev->next = node;
		ptr = node;
	}
}

template<class T>
void
SListManipulator<T>::Delete()
{
	assert(ptr);

	if (prev)
	{
		prev->next = ptr->next;
		delete ptr;
		ptr = prev->next;
	} else {
		list->head = ptr->next;
		delete ptr;
		ptr = list->head;
	}
}

#endif
